/*
求幂集
*/

#include<iostream>
#include<vector>
using namespace std;

// 解法对象
class Solution {
public:
	
	// 求所有幂集
	vector<vector<int>> subsets(vector<int>& nums)
	{
		// 存放幂集
		vector<vector<int>> Mi;
		
		// 存放M1
		vector<vector<int>> Mi_1={{},{nums[0]}};	
		
		// 长度为1
		if(nums.size()==1) return Mi_1;
		
		// 遍历数组
		for(int i=1; i<nums.size(); i++)
		{
			// 向Mi_1中每个集合元素末尾添加e
			vector<vector<int>> Ai = appendi(Mi_1, nums[i]);
			Mi = Mi_1;
			
			// 将Ai所有集合元素添加到Mi中
			for(int j=0; j<Ai.size(); j++)
				Mi.push_back(Ai[j]);
			
			Mi_1 = Mi;
		}
		return Mi;
	}
	
	// 向Mi_1中每个集合元素末尾添加e
	vector<vector<int>> appendi(vector<vector<int>> Mi_1, int e)	
	{
		vector<vector<int>> Ai=Mi_1;
		for(int j=0; j<Ai.size(); j++)
			Ai[j].push_back(e);
		return Ai;
	}
};

// 输出幂集
void disp(vector<vector<int>> ans)
{
	printf("    ");
	for(auto it=ans.begin();it!=ans.end();it++)
	{
		if((*it).size()==0)
			printf("{} ");
		else
		{
			printf("[");
			for(int j=0;j<(*it).size();j++)
				if(j==0)
					printf("%d",(*it)[j]);
				else
					printf(" %d",(*it)[j]);
			printf("]  ");
		}
	}
	printf("\n");
}

int main()
{
	// 初始化数组
	vector<int> nums={1, 2, 3};
	
	// 存储幂集
	vector<vector<int>> ans;
	
	// 获取幂集
	printf(" 幂集如下:\n  ");
	Solution obj;
	ans = obj.subsets(nums);
	
	// 打印幂集
	disp(ans);
	return 0;
}
